package leetcode;
/**
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 
 * 说明：每次只能向下或者向右移动一步。
 * 
 * @author maodou38
 *
 */
public class Solution64_mime_2 {
	//二维动态矩阵 假设dp中每格为到右下角的最短距离
	public int minPathSum(int[][] grid) {
		int[][] dp=new int[grid.length][grid[0].length];
		for(int i=grid.length-1;i>=0;i--) {//横
			for(int j=grid[0].length-1;j>=0;j--) {//纵
				if(i==grid.length-1&&j!=grid[0].length-1) {//只能往右走
					dp[i][j]=grid[i][j]+dp[i][j+1];
				}else if(j==grid[0].length-1&&i!=grid.length-1) {//只能往下走
					dp[i][j]=grid[i][j]+dp[i+1][j];
				}else if(i!=grid.length-1&&j!=grid[0].length-1){//两边都可以走
					dp[i][j]=Math.min(dp[i+1][j], dp[i][j+1])+grid[i][j];
				}else {//到达终点
					dp[i][j]=grid[i][j];
				}
			}
		}
		return dp[0][0];
	}
}
